package algocasts;

public class P9_reverseList {
    class ListNode {
        int val;
        ListNode next;
    }

    // Time:O(n) Space:O(1)
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        // 当当前指向节点不为空
        while (cur != null) {
            ListNode next = cur.next;   // 先保存当前节点的下一个节点
            cur.next = pre; // 当前节点指向前一个节点
            pre = cur;  // 前一个节点指向当前节点
            cur = next; // 当前节点变为下一个
        }
        return pre; // 最后返回的就是翻转之后的头节点
    }
}
